import com.sun.corba.se.spi.orb.ParserImplBase;
import javafx.scene.chart.StackedAreaChart;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        System.out.println("before: " + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("after: " + Arrays.toString(arr));
    }

    public static void heapSort(int[] arr) {
        int len = arr.length;
        heapify(arr);
        for (int i = len - 1; i >= 0; i--) {
            swap(arr, 0, i);
            siftDown(arr, 0, i - 1);
        }
    }

    public static void heapify(int[] arr) {
        int len = arr.length;
        for (int i = len / 2 - 1; i >= 0; i--) {
            siftDown(arr, i, len - 1);
        }
    }

    public static void siftDown(int[] arr, int l, int r) {
        int idx = l * 2 + 1;
        while (idx <= r) {
            if (idx + 1 <= r && arr[idx] < arr[idx + 1]) {
                idx++;
            }
            if (arr[l] < arr[idx]) swap(arr, idx, l);
            else break;
            l = idx;
            idx = l * 2 + 1;
        }
    }

    public static void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }

}
